package com.LeeCode;

/**
 * 使二进制字符串字符交替的最少反转次数
 */

public class Code1888 {
    public static void main(String[] args) {
        String s = "100";
        System.out.println(new Code1888().minFlips(s));
    }

    public int minFlips(String s) {
        int n = s.length();
        s += s;
        int m = s.length();
        int even_1 = 0, even_0 = 0; // 偶数
        int odds_1 = 0, odds_0 = 0; // 奇数
        int res = Integer.MAX_VALUE - 1;

        for (int i = 0; i < m; i++) {
            //入
            int now = s.charAt(i) - '0';
            if (i % 2 == 0) {
                if (now == 0) even_0++;
                if (now == 1) even_1++;
            } else {
                if (now == 0) odds_0++;
                if (now == 1) odds_1++;
            }

            if (i < n - 1) continue;

            // 更新
            int temp = Math.min(even_0 + odds_1, even_1 + odds_0);
            res = Math.min(temp, res);

            // 出
            int pos = i - n + 1;
            now = s.charAt(pos) - '0';
            if (pos % 2 == 0) {
                if (now == 0) even_0--;
                if (now == 1) even_1--;
            } else {
                if (now == 0) odds_0--;
                if (now == 1) odds_1--;
            }
        }
        return res;
    }
}
